package com.lwx.setAndMap;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * BinarySearchTree二分搜索树
 * @param <K> 二分搜索树的节点必须是可以比较的
 */
public class BSTKV<K extends Comparable<K>,V> {
    /**
     * 二叉搜索树的Node节点是一个私有类，没有必要向外部泄露
     */
    private class Node{
        private K key;
        private V value;
        private Node leftNode, rightNode;
        public Node(K key,V value){
            this.key = key;
            this.value = value;
            leftNode = null;
            rightNode = null;
        }
    }

    private Node root;
    private int size;
    public BSTKV(){
        root = null;
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size== 0;
    }

    public V get(K key){
        if(root == null){
            throw new IllegalArgumentException("BST is empty");
        }
        Node node = get(root, key);
        if(node == null){
            throw new IllegalArgumentException("BST doesn't contain "+key);
        }
        return node.value;
    }

    //从以node为根节点的树上，找到key,node.key == key的节点
    private Node get(Node node,K key){
        if(node == null){
            return null;
        }else if(node.key.equals(key)){
            return node;
        }else if(key.compareTo(node.key)<0){
           return get(node.leftNode, key);
        }else {
            return get(node.rightNode, key);
        }
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        preOrder(root);
    }


    /**
     * 遍历以node为根节点树
     * @param node
     */
    private void preOrder(Node node){
        if(node == null){
            return;
        }
        //访问该节点
        System.out.println("["+node.key+","+node.value+"]");
        preOrder(node.leftNode);
        preOrder(node.rightNode);
    }

    //非递归的方式进行前序遍历,需要压栈
    //右孩子先入栈，左孩子再入栈
    //操作元素时，只能操作从栈中弹出来的元素
    public void preOrederNR(){
        Stack<Node> stack = new Stack();
        //先入栈，只能访问从栈中弹出来的元素
        stack.push(root);
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            //访问弾栈出来的元素
            //要访问的元素都是从栈中弹出来的元素
            System.out.println(cur.key);
            //右节点先入栈，左节点再入栈
            if(cur.rightNode != null){
                stack.push(cur.rightNode);
            }
            if(cur.leftNode != null){
                stack.push(cur.leftNode);
            }
        }
    }
    /**
     * 二叉搜索树添加新元素
     * Node对用户屏蔽，所以不应该作为公共方法的参数
     * @param
     */
    public void add(K key,V value){
        this.root = add(root, key,value);
    }

    public boolean contains(K e){
        return contains(root, e);
    }

    private boolean contains(Node node, K e){
        if(node == null){
            return false;
        }
        if(e.compareTo(node.key) == 0){
            return true;
        }else if(e.compareTo(node.key)<0){
            return contains(node.leftNode, e);
        }else {
            return contains(node.rightNode, e);
        }
    }

    /**
     * 我的实现方法，相对没有那么好理解
     * @param node
     * @param e
     */
//    private void add(Node node, T e){
//        if(e.equals(node.e)){
//            return;
//        }else  if(e.compareTo(node.e)<0){
//            if(Objects.isNull(node.leftNode)){
//                node.leftNode = new Node(e);
//                size ++;
//                return;
//            }else {
//                add(node.leftNode, e);
//            }
//        }else {
//            if(Objects.isNull(node.rightNode)){
//                node.rightNode = new Node(e);
//                size ++;
//                return;
//            }else {
//                add(node.leftNode, e);
//            }
//        }
//    }

    /**
     * 老师的实现方法，相对比较容易理解
     * 返回插入新节点后二分搜索树的根
     * @param node  当前二分搜索树的根
     * @param
     */
    private Node add(Node node, K key, V value){
        //退出条件，对于树的任何一个节点都成立
        if(node == null){
            size++;
            return new Node(key,value);
        }

        //进行递归
        //e.compareTo(node.e)==0时，不进行插入
        if(key.compareTo(node.key)<0){
            node.leftNode = add(node.leftNode, key, value);
        }else if(key.compareTo(node.key)>0){
            node.rightNode = add(node.rightNode, key, value);
        }
        return node;
    }

    /**
     * 用非递归的方法实现二叉搜索树
     * @param
     */
//    public void add(T e){
//        if(this.root == null){
//            this.root = new Node(e);
//            return;
//        }else {
//            if(e.compareTo(root.e)<0 && Objects.isNull(root.leftNode)){
//                root.leftNode = new Node(e);
//            }else if(e.compareTo(root.e)>0 && Objects.isNull(root.rightNode)){
//                root.rightNode = new Node(e);
//            }else {
//                Node current = root;
//                Node parent = root;
//                while (!Objects.isNull(current)){
//                    parent = current;
//                    if(e.compareTo(current.e)<0){
//                        current = parent.leftNode;
//                    }else {
//                        current = parent.rightNode;
//                    }
//                }
//                if(e.compareTo(parent.e)<0){
//                    parent.leftNode = new Node(e);
//                }else {
//                    parent.rightNode = new Node(e);
//                }
//            }
//        }
//    }

    //层序遍历
    public void levelOrder(){
        Queue<Node> queue = new LinkedList();
        queue.add(root);
        while (queue.size()>0){
            Node cur = queue.remove();
            System.out.println(cur.key+","+cur.value);
            if(cur.leftNode != null){
                queue.add(cur.leftNode);
            }
            if(cur.rightNode != null){
                queue.add(cur.rightNode);
            }
        }
    }

    //删除最小值，并返回最小值
    //在没有指定最小值为谁的情况下，删除完成要将最小值返回
    public V removeMin(){
        V e = minimum();
        root = removeMin(root);
        return e;
    }

    public V removeMax(){
        V e = maximum();
        root = removeMax(root);
        return e;
    }

    //删除以node为根的BST
    //返回删除这个节点后新的的BST的根
    //哪个是新的BST的根节点
    //有返回值一般要解决父节点子节点的想法
    private Node removeMin(Node node){
        //递归到底的情况
        if(node.leftNode == null){
            Node right = node.rightNode;
            node.rightNode = null;
            size --;
            return right;
        }

        node.leftNode = removeMin(node.leftNode);
        return node;
    }

    private Node removeMax(Node node){
        //递归到底的情况
        if(node.rightNode == null){
            Node left = node.leftNode;
            node.leftNode = null;
            size --;
            return left;
        }
        node.rightNode = removeMin(node.rightNode);
        return node;
    }

    //1.只有左孩子
    //2.只有右孩子
    //3.既有左孩子也有右孩子，该节点左子树的最大节点/该节点右子树的最小节点
    public V remove(K e){
        V value = get(e);
        root = remove(root, e);
        return value;
    }


    /**
     * 删除以node为根节点，并且值为e的BST
     * @param node
     * @param e
     * @return 被删除BST的根节点
     */
    private Node remove(Node node, K e){
        if(node == null){
            return null;
        }

        if(e.compareTo(node.key)<0){
            node.leftNode = remove(node.leftNode, e);
            return node;
        }else if(e.compareTo(node.key)>0){
            node.rightNode = remove(node.rightNode, e);
            return node;
        }else {     //e == node.e
            //左子树为空
            if(node.leftNode == null){
                Node right = node.rightNode;
                node.rightNode = null;
                size--;
                return right;
            }
            //右子树为空
            if(node.rightNode == null){
                Node left = node.leftNode;
                node.leftNode = null;
                size--;
                return left;
            }

            //左右子树都不为空，找到右子树的最小值successor，用successor顶替被删除节点
            if(node.leftNode != null && node.rightNode != null){
                //1.找到右子树的最小值successor
                Node successor = minimum(node.rightNode);
                //2.将successor挂接在node的父节点上
                successor.rightNode = removeMin(node.rightNode);
                successor.leftNode = node.leftNode;

                node.leftNode = node.rightNode = null;
                return successor;
            }
        }
        return node;
    }




    public V minimum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is NULL");
        }
        Node miniNode = minimum(root);
        return miniNode.value;
    }

    //返回以node为根节点的最小值
    private Node minimum(Node node){
        if(node.leftNode == null){
            return node;
        }
        return minimum(node.leftNode);
    }

    public V maximum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is NULL");
        }
        Node maxNode = maximum(root);
        return maxNode.value;
    }

    //返回以node为根节点的最大值
    private Node maximum(Node node){
        if(node.rightNode == null){
            return node;
        }
        return minimum(node.rightNode);
    }
}

